

// 查找连续性最强的子序列
// 贪心算法 + 二分查找

function getSequence(arr) {
    // 结果集 存放的是索引
    const result = [0] 
    // 用于存放索引
    const p = result.slice(0)
    // 二分查找
    let start, end, middle;
    const len = arr.length
    for(let i = 0; i < len; i++) {
        const arrI = arr[i]
        if(arrI !== 0) { // 这个判断是为了在 vue3 中处理掉数组的 0 的情况，因为 0 表示新增的 
            let resultLastIndex = result[result.length - 1] // 获取结果集最后一个arr中的索引
            if(arr[resultLastIndex] < arrI) {
                // 正常放入的时候，前一个节点索引就是 result 中的最后一个
                p[i] = result[result.length - 1]
                // 将当前的索引放入到结果集中即可
                result.push(i)
                continue
            }
        }
        // 二分查找替换
        start = 0
        end = result.length - 1 
        while(start < end) {
            middle = ((start + end) / 2) | 0 // | 0 表示向下取证
            if(arr[result[middle]] < arrI) {
                start = middle + 1
            } else {
                end = middle
            }
        }
        if(arrI < arr[result[start]]) {
            // 进行替换, 找到是那个节点的前一个
            p[i] = result[start - 1]
            result[start] = i
        }
    }
    // p 为前驱节点列表，需要根据最后一个节点做追随
    let l = result.length
    let last = result[l - 1]
    while(l-- > 0) {
        result[l] = last
        last = p[last]
    }
    // 需要创建一个 前驱节点 进行倒叙追溯 (因为最后一项 是不会错的)
    // console.log(p)
    return result
}

// console.log(getSequence([2, 6, 7, 8, 9, 11]))
console.log(getSequence([2, 3, 1, 5, 6, 8, 7, 9, 4]))